home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / graph / _g_update.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  4.0 KB  |  194 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _g_update.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. #include <LEDA/graph.h>
  18.  
  19.  
  20. list<edge> graph::insert_reverse_edges()
  21. { list<edge> L;
  22.   edge e = first_edge();
  23.  
  24.   if (e != nil)
  25.   { L.append(new_edge(e->t,e->s,e->data[0]));
  26.     copy_edge_entry(e->data[0]);
  27.     e = succ_edge(e);
  28.    }
  29.  
  30.   edge stop = last_edge();
  31.  
  32.   while (e != stop);
  33.   { L.append(new_edge(e->t,e->s,e->data[0]));
  34.     copy_edge_entry(e->data[0]);
  35.     e = succ_edge(e);
  36.    } 
  37.  
  38.   return L;
  39. }
  40.  
  41.  
  42. void graph::reset()  const   // reset all iterators
  43. { node v;
  44.   forall_nodes(v,*this) v->adj_iterator=nil;
  45. }
  46.  
  47. node graph::new_node(GenPtr i)
  48. { 
  49.   node v = new node_struct(i); 
  50.   v->g = this;
  51.   v->name = ++max_n_index;
  52.   aux_link(v)->succ_link = nil;
  53.   V.append(node_link(v));
  54.   return v;
  55. }
  56.  
  57. void graph::del_node(node v)
  58. { if (v->g != this) error_handler(4,"del_node: v is not in G");
  59.  
  60.  
  61.   // delete adjacent edges
  62.   while (outdeg(v) != 0) del_edge(first_adj_edge(v));
  63.   while (indeg(v) != 0) del_edge(first_in_edge(v));
  64.  
  65.  
  66.   V.del(node_link(v));
  67.  
  68.   if (parent==0)   // no subgraph
  69.     clear_node_entry(v->data[0]);
  70.  
  71.   delete v;
  72. }
  73.  
  74. edge graph::new_edge(node v, node w, GenPtr i)
  75. { if ((v->g!=this) || (w->g!=this)) 
  76.       error_handler(6, "G.new_edge(v,w): v or w not in G");
  77.   edge e = new edge_struct(v,w,i);
  78.   e->name = ++max_e_index;
  79.   E.append(edge_link(e));
  80.   v->adj_edges[0].append(adj_link1(e));
  81.   w->adj_edges[1].append(adj_link2(e));
  82.   return e ; 
  83. }
  84.  
  85. edge graph::new_edge(edge e1, node w, GenPtr i, int dir)  
  86. { //add edge (source(e1),w) after/before e1 to adjacency list of source(e1)
  87.  
  88.   node v  = e1->s;
  89.  
  90.   if ((v->g!=this) || (w->g!=this)) 
  91.      error_handler(9,"G.new_edge(e,w): e or w not in G");
  92.  
  93.   edge e = new edge_struct(v,w,i);
  94.  
  95.   e->name = ++max_e_index;
  96.   E.append(edge_link(e));
  97.   v->adj_edges[0].insert(adj_link1(e),adj_link1(e1),dir);
  98.   w->adj_edges[1].append(adj_link2(e));
  99.   return e ; 
  100. }
  101.  
  102. edge graph::new_edge(edge e1, edge e2, GenPtr i, int dir1, int dir2)  
  103. { //add edge (source(e1),target(e2)) 
  104.   //after(dir=0)/before(dir=1) e1 to out-list of source(e1)
  105.   //after(dir=1)/before(dir=1) e2 to in-list of target(e2)
  106.  
  107.   node v  = e1->s;
  108.   node w  = e2->t;
  109.  
  110.   if ((v->g!=this) || (w->g!=this)) 
  111.      error_handler(9,"G.new_edge(e,w): e or w not in G");
  112.  
  113.   edge e = new edge_struct(v,w,i);
  114.  
  115.   e->name = ++max_e_index;
  116.   E.append(edge_link(e));
  117.   v->adj_edges[0].insert(adj_link1(e),adj_link1(e1),dir1);
  118.   w->adj_edges[1].insert(adj_link2(e),adj_link1(e2),dir2);
  119.   return e ; 
  120. }
  121.  
  122.  
  123. void graph::del_edge(edge e)
  124. { node v = e->s;
  125.   node w = e->t;
  126.  
  127.   if (v->g != this) error_handler(10,"del_edge: e is not in G");
  128.      
  129.   E.del(edge_link(e));
  130.  
  131.   v->adj_edges[0].del(adj_link1(e));
  132.   w->adj_edges[1].del(adj_link2(e));
  133.  
  134.   if (parent == 0)  // no subgraph
  135.      clear_edge_entry(e->data[0]);
  136.  
  137.   delete e; 
  138. }
  139.  
  140.  
  141. void graph::hide_edge(edge e)
  142. { adj_link1 l1 = adj_link1(e);
  143.   if (l1->succ_link != l1)
  144.   { e->s->adj_edges[0].del(l1);
  145.     e->t->adj_edges[1].del(adj_link2(e));
  146.     l1->succ_link = l1;
  147.    }
  148.  
  149.  }
  150.  
  151. void graph::restore_edge(edge e)
  152. { adj_link1 l1 = adj_link1(e);
  153.   if (l1->succ_link == l1) 
  154.   { e->s->adj_edges[0].append(l1);
  155.     e->t->adj_edges[1].append(adj_link2(e));
  156.    }
  157.  }
  158.  
  159.  
  160. edge graph::rev_edge(edge e)
  161. { node v = e->s;
  162.   node w = e->t;
  163.   if (v->g != this) error_handler(11,"rev_edge: e is not in G");
  164.  
  165.   v->adj_edges[0].del(adj_link1(e));
  166.   w->adj_edges[1].del(adj_link2(e));
  167.  
  168.   w->adj_edges[0].append(adj_link1(e));
  169.   v->adj_edges[1].append(adj_link2(e));
  170.  
  171.   e->s = w;
  172.   e->t = v;
  173.   return e; 
  174. }
  175.  
  176. graph& graph::rev()              
  177. { edge e;
  178.   forall_edges(e,*this) rev_edge(e);
  179.   return *this; 
  180. }
  181.  
  182. void graph::del_all_nodes() { clear(); }
  183.  
  184. void graph::del_all_edges()
  185. { node v;
  186.   forall_nodes(v,*this) 
  187.   { v->adj_edges[0].clear();
  188.     v->adj_edges[1].clear();
  189.    }
  190.   while (!E.empty()) delete edge(edge_link(E.pop()));
  191.   max_e_index = -1;
  192. }
  193.  
  194.